package cn.zifangsky.sort;

/**
 * 希尔排序
 *
 * @author zifangsky
 * @date 2019/1/3
 * @since 1.0.0
 */
public class ShellSort {

    /**
     * 希尔排序
     * <p><b>最坏时间复杂度：</b>O(n^2)</p>
     * @author zifangsky
     * @date 2019/1/3 17:56
     * @since 1.0.0
     * @param array 待排序数组
     */
    public static int[] sort(int[] array){
        if(array == null || array.length < 1){
            throw new IllegalArgumentException("Illegal initial array");
        }

        int length = array.length;

        //使用增量gap = gap / 2
        for(int gap = (length / 2); gap > 0; gap = gap / 2){
            //对于每个增量，对数组使用插入排序
            for(int i = gap; i < length; i = i + gap){
                int temp = array[i];

                int j;
                for(j = (i - gap); j >= 0 && temp < array[j]; j = j - gap) {
                    //如果temp < array[j]，则array[j]向右移动gap位
                    array[j + gap] = array[j];
                }
                //将temp放到正确位置
                array[j + gap] = temp;
            }
        }

        return array;
    }

}
